export function letterCombinations (digits: string): string[] {
    const combinations: string[] = [];
    const combination: string[] = [];
    const digitMap = new Map<string, string>();
    digitMap.set('2', 'abc');
    digitMap.set('3', 'def');
    backTrack(combinations, digitMap, 0, digits, combination);
    return combinations;
}

function backTrack (combinations: string[], digitMap: Map<string, string>, index: number, digits: string, combination: string[]) {
    if (index === digits.length) {
        combinations.push(combination.join(''));
    } else {
        const chars = digitMap.get(digits[index])!;
        for (let i = 0; i < chars.length; i++) {
            combination.push(chars[i]);
            backTrack(combinations, digitMap, index+1, digits, combination);
            combination.pop();
        }
    }
}